class Solution {
public:
    vector<int> memo;
    string str;
    int numDecodings(string s) {
        str = s;
        memo = vector<int>(s.length(), 0);
        return dp(0);
    }
    int dp(int i) {
        if (i == str.size()) return 1;
        if (memo[i]) return memo[i];
        if (i < str.size() && str[i] == '0')
        {
            memo[i] = 0;
            return 0;
        }
        if (i == str.size() - 1) return 1;
        if ((str[i] == '1') || (str[i] == '2' && str[i + 1] >= '0' && str[i + 1] <= '6'))
            memo[i] = dp(i + 1) + dp(i + 2);
        else
            memo[i] = dp(i + 1);
        return memo[i];
    }
};
